package sysu.el.graph.undi.algor;

import sysu.el.array.Bomb;
import sysu.el.array.BoolArray;
import sysu.el.array.algors.Sig;
import sysu.el.array.ints.ArrInt;
import sysu.el.graph.GTMatrix;
import sysu.el.graph.tree.ChildrenTreeTopo;
import sysu.el.graph.tree.FCTreeTopo;
import sysu.el.graph.tree.FatherTreeTopo;
import sysu.el.graph.tree.FatherTreeTopoInt;
import sysu.el.graph.undi.UndiGT;
import sysu.el.matrix.ints.MatInt;

public class MSTCreatorV0 {
	public UndiGT graph;
	public BoolArray isVisited;
	public MSTCreatorV0(UndiGT g){
		graph = g;
		isVisited = new BoolArray(g.getNodeNum());
		ftt = new FatherTreeTopoInt(g.getNodeNum());
	}
	
	public void getTree(int node){
		
	}

	public FatherTreeTopo ftt;
	public static FCTreeTopo getTree(FCTreeTopo fc, int node){
		FCTreeTopo newFC = new FCTreeTopo(node);
		ChildrenTreeTopo ct = fc.ct;
		
		while (node == 0){
			
		}
		
		return newFC;
	}
	
	/**
	 * Relevant of the isVisited
	 * @param root
	 * @return The tree have a value... 
	 * primitive type of ft in the return value is FatherTreeTopoInt 
	 * you should cast FatherTreeTopo to FatherTreeTopoInt then you got a value
	 */
	public FCTreeTopo createOneTree(int root){
		FatherTreeTopoInt ft = new FatherTreeTopoInt(graph.getNodeNum(), Integer.MAX_VALUE);
		ChildrenTreeTopo ct = new ChildrenTreeTopo(graph.getNodeNum());
		isVisited.reset();
		ct.root = root;
		ft.fa[root] = root;
		ft.val[root] = 0;
		int cur = root;
//		int newCur = root;
//		for (int i=0; i<graph.getNodeNum()-1; i++){
//		for (Bomb.c4.start(graph.getNodeNum()-1); Bomb.c4.survive(); Bomb.c4.tick()){
//		for (int i=graph.getNodeNum()-1; i>0; i--){
		
		int counter = graph.getNodeNum() - 1;
		do{
			// Update
			isVisited.setVisited(cur);
			for (int j=graph.getDegree(cur)-1; j>=0; j--){
				int id = graph.getList(cur)[j];
				if ((isVisited.isUnvisited(id))	&& (ft.val[id] > graph.getW(cur, id))
						/*||(ft.val[id]==0)*/	){
					ft.val[id] = graph.getW(cur, id);
					ft.fa[id] = cur;
				}
			}
			System.out.println(Sig.mkString(ft.fa, ", "));
			int minId = -1;
			int minVal = Integer.MAX_VALUE;
			for (int j=graph.getNodeNum()-1; j>=0; j--){
				if ((isVisited.isUnvisited(j) && (ft.val[j] < minVal))){
					minId = j;
					minVal = ft.val[j];
				}
			}
			
			ct.addEdge(ft.fa[minId], minId);
			ft.sum += minVal;
			cur = minId;
		}while(--counter > 0);

		return new FCTreeTopo(ft, ct);
	}
}
